// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-07 13:18
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

public class Tree2str {
    /**
     * 使用括号对实现对二叉树的表示
     */
    StringBuilder builder = new StringBuilder();

    public String tree2str(TreeNode root) {
        // 对于不影响输入输出一对一映射关系的括号可以省略
        // 根据观察 -> 括号内部的括号中第一个空括号不可以省略
        // 节点为叶子节点不需要插入括号 -> 节点为空节点需要插入括号
        search(root);
        return simple();
    }

    private String simple() {
        // 删除字符串中括号内的非第一个空字符串 -> (a) -> ()
        // 即删除前面字符是右括号的空括号
        // 使用正则表达式
        // 去除字符串开头第一个括号
        builder.deleteCharAt(0);
        builder.deleteCharAt(builder.length() - 1);
        for (int i = 0; i < builder.length(); i++) {
            if (i > 0 && builder.charAt(i) == '(' && builder.charAt(i - 1) == ')' && builder.charAt(i + 1) == ')') {
                builder.deleteCharAt(i);
                // builder 删除字符之后序号会发生变化
                builder.deleteCharAt(i);
            }
        }
        return builder.toString();
    }

    /**
     * 通过对树的遍历实现对结果字符串的编写
     *
     * @param root 根节点
     */
    private void search(TreeNode root) {
        if (root == null) {
            // 当前节点为空节点,传入的节点不能为空节点
            builder.append("()");

        } else {
            if (root.left == null && root.right == null) {
                // 当前节点为叶子节点
                builder.append('(');
                builder.append(root.val);
                builder.append(')');
            } else {
                // 当前节点为非叶子节点
                builder.append('(');
                builder.append(root.val);

                search(root.left);


                search(root.right);

                builder.append(')');
            }


        }


    }


    @Test
    public void shout() {
        int[] nodesT = {1, 2, 3, 4};
//        int[] nodesT = {1, 2, 3, -1, 4};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodesT);
        System.out.println(tree2str(root));
    }
}
